package jjn.round1;

/**
 * @author Jjn
 * @since 2022-08-07 15:51
 */
public class LeetCode1051_HeightChecker {
    
    public int heightChecker(int[] heights) {
        int[] array = copyArray(heights);
        quickSort(heights, 0, heights.length - 1);
        int notEqualCount = 0;
        for (int i = 0; i < heights.length; i++) {
            if (array[i] != heights[i]) {
                notEqualCount++;
            }
        }
        return notEqualCount;
    }
    
    private int[] copyArray(int[] heights) {
        int[] data = new int[heights.length];
        System.arraycopy(heights, 0, data, 0, heights.length);
        return data;
    }
    
    public static void quickSort(int[] arr, int low, int high) {
        if (arr.length == 0) return;
        if (low >= high) return;
        int left = low;
        int right = high;
        
        int temp = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= temp) {
                right--;
            }
            arr[left] = arr[right];
            
            while (left < right && arr[left] <= temp) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = temp;
        quickSort(arr, low, left - 1);
        quickSort(arr, left + 1, high);
    }
    
}
